package com.zjj.algorithm.learning.leetcode.queue;

/**
 * 264. 丑数 II 中档题
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 *
 * 示例 1：
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 *
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 * @author zjj_admin
 * @date 2022/11/3 10:59
 */
public class UglyNumber {

    public static void main(String[] args) {

        int number = nthUglyNumber(10001);
        System.out.println("number = " + number);

    }

    public static int nthUglyNumber(int n) {
        int[] res = new int[n];
        res[0] = 1;
        if(n == 1){
            return 1;
        }
        int _2 = 0;
        int _3 = 0;
        int _5 = 0;
        int loc = 1;
        for (int i = 1; i < n; i++) {
            int ans2 = res[_2] * 2;
            int ans3 = res[_3] * 3;
            int ans5 = res[_5] * 5;
            int min = Math.min(ans2,Math.min(ans3,ans5));
            res[loc] = min;
            loc ++;
            if(ans2 == min){
                _2 ++;
            }
            if(ans3 == min){
                _3 ++;
            }
            if (ans5 == min){
                _5 ++;
            }
        }

        return res[n - 1];
    }
}
